#include <stdio.h>
#include <stdbool.h> // bool
// #include <search.h> // qsort
#include <malloc.h> // malloc
#include <string.h> // memset


// 方法一：回溯
static bool dfs(int index, int *matchsticks, int matchsticksSize, int *edges, int len) {
    if (index == matchsticksSize) {
        return true;
    }
    for (int i = 0; i < 4; i++) {
        edges[i] += matchsticks[index];
        if (edges[i] <= len && dfs(index + 1, matchsticks, matchsticksSize, edges, len)) {
            return true;
        }
        edges[i] -= matchsticks[index];
    }
    return false;
}

static int cmp(const void *pa, const void *pb) {
    return *(int *)pb - *(int *)pa;
}

bool makeSquare(int* matchsticks, int matchsticksSize) {
    int totalLen = 0;
    for (int i = 0; i < matchsticksSize; i++) {
        totalLen += matchsticks[i];
    }
    if (totalLen % 4 != 0) {
        return false;
    }
    qsort(matchsticks, matchsticksSize, sizeof(int), cmp);
    int edges[4] = {0, 0, 0, 0};
    return dfs(0, matchsticks, matchsticksSize, edges, totalLen / 4);
}

// 方法二：状态压缩 + 动态规划
bool makeSquare2(int* matchsticks, int matchsticksSize) {
    int totalLen = 0;
    for (int i = 0; i < matchsticksSize; i++) {
        totalLen += matchsticks[i];
    }
    if (totalLen % 4 != 0) {
        return false;
    }
    int len = totalLen / 4, n = matchsticksSize;
    int *dp = (int *)malloc(sizeof(int) * (1 << n));
    memset(dp, -1, sizeof(int) * (1 << n));
    dp[0] = 0;
    for (int s = 1; s < (1 << n); s++) {
        for (int k = 0; k < n; k++) {
            if ((s & (1 << k)) == 0) {
                continue;
            }
            int s1 = s & ~(1 << k);
            if (dp[s1] >= 0 && dp[s1] + matchsticks[k] <= len) {
                dp[s] = (dp[s1] + matchsticks[k]) % len;
                break;
            }
        }
    }
    bool res = dp[(1 << n) - 1] == 0;
    free(dp);
    return res;
}


// int main() {
//     // 报错的，这个都不知道哦怎么调用的？？？
//     int* matchsticks = {1,1,2,2,2};
//     int length = sizeof(matchsticks) / sizeof(matchsticks[0]);
//     // int matchsticksSize = (int) malloc(sizeof(int) * length);
//     bool res = makeSquare(matchsticks, length);
//     printf("%c", res);
// }